The Problem

The Same Fringe problem is to write a function that compares the leaves of two binary trees. If both trees have the same string of leaves, the function sameFringe should return true, otherwise the function should return false.

The internal structure of the trees does not matter; therefore, an approach that works recursively on the structure of the trees will always be a bad fit for one of the two trees. Same Fringe is a good problem to test the expressiveness of languages with iterators. We will see that we can get a perfectly good solution in Pizza without needing any iterators at all.

The Java Solution

?

The Pizza Solution
Let's start with the definition of a binary tree. A tree is defined by two cases: It is either a leaf with an element, or it is a branch with a left tree and a right tree.

Next, let's define the fringe of a tree as an enumerator (see last week's problem). This is easily done by pattern matching on the form of the tree at hand:

Enumerator<A> eagerFringe(Tree<A> t) { switch (t) { case Leaf(a elem): return new SingletonEnumerator(elem); case Branch(Tree<a> l, Tree<a> r): return eagerFringe(l).concat(eagerFringe(l)); } }

If the tree is a leaf, return an enumerator that yields the element of the leaf and afterwards terminates. See pizza.util.SingletonEnumerator for a definition of a SingletonEnumerator. On the other hand if the tree is a branch, we concatenate the fringes of the two subtree, using the function concat in pizza.util.Enumerator.

This works, but a problem is that the fringe enumerator is built up immediately and requires storage proportional to the size of a tree. A solution that runs in less space computes the fringe of the tree lazily, only when it is demanded. To this purpose, we write a new class DelayedEnumerator. The constructor for this class is passed a parameter-less function which returns an enumeration when called. This "suspension" is called whenever the first element of the enumeration demanded. The suspension is called only once, since after it's first call its result is cached in the value field.

We make use of this Enumerator abstraction in function fringe, which compute the fringe of its tree argument on demand.

Once we have the fringes of two trees as Enumerators, comparing them is straightforward: Simply compare corresponding elements with Java's equal method, defined in class Object. Since equal is defined only in class Object, we must restrict the range of the type variable A to subtypes of Object. Hence, the sameFringe function cannot be applied to trees of int's, say, since int does not have an equals method. defined.

The test program compares the fringes of two trees of String and two trees of Integers.

Sources for the example programs are found in

pizza/src/examples/samefringe.{java,pizza}

in the pizza distribution (version 0.28b or higher). Sources for the library modules are found in

pizza/src/pizza/util.

Page design & maintenance: John Maraist.
Java is a trademark of Sun Microsystems.